.TH std::ranges::sort_heap 3 "2024.06.10" "http://cppreference.com" "C++ Standard Libary"
.SH NAME
std::ranges::sort_heap \- std::ranges::sort_heap

.SH Synopsis
   Defined in header <algorithm>
   Call signature
   template< std::random_access_iterator I, std::sentinel_for<I> S,

             class Comp = ranges::less, class Proj = std::identity >
   requires std::sortable<I, Comp, Proj>                              \fB(1)\fP \fI(since C++20)\fP
   constexpr I

       sort_heap( I first, S last, Comp comp = {}, Proj proj = {} );
   template< ranges::random_access_range R, class Comp =
   ranges::less,

             class Proj = std::identity >                             \fB(2)\fP \fI(since C++20)\fP
   requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
   constexpr ranges::borrowed_iterator_t<R>

       sort_heap( R&& r, Comp comp = {}, Proj proj = {} );

   Converts the max heap [first, last) into a sorted range in ascending order. The
   resulting range no longer has the heap property.

   1) Elements are compared using the given binary comparison function comp and
   projection object proj.
   2) Same as \fB(1)\fP, but uses r as the range, as if using ranges::begin(r) as first and
   ranges::end(r) as last.

   The function-like entities described on this page are niebloids, that is:

     * Explicit template argument lists cannot be specified when calling any of them.
     * None of them are visible to argument-dependent lookup.
     * When any of them are found by normal unqualified lookup as the name to the left
       of the function-call operator, argument-dependent lookup is inhibited.

   In practice, they may be implemented as function objects, or with special compiler
   extensions.

.SH Parameters

   first, last - the range of elements to sort
   r           - the range of elements to sort
   pred        - predicate to apply to the projected elements
   proj        - projection to apply to the elements

.SH Return value

   An iterator equal to last.

.SH Complexity

   Given N = ranges::distance(first, last), at most \\(\\scriptsize 2N\\log{(N)}\\)2Nlog(N)
   comparisons and \\(\\scriptsize 4N\\log{(N)}\\)4Nlog(N) projections.

.SH Notes

   A max heap is a range of elements [f, l), arranged with respect to comparator comp
   and projection proj, that has the following properties:

     * With N = l - f, p = f[(i - 1) / 2], and q = f[i], for all 0 < i < N, the
       expression std::invoke(comp, std::invoke(proj, p), std::invoke(proj, q))
       evaluates to false.
     * A new element can be added using ranges::push_heap, in \\(\\scriptsize
       \\mathcal{O}(\\log N)\\)𝓞(log N) time.
     * The first element can be removed using ranges::pop_heap, in \\(\\scriptsize
       \\mathcal{O}(\\log N)\\)𝓞(log N) time.

.SH Possible implementation

struct sort_heap_fn
{
    template<std::random_access_iterator I, std::sentinel_for<I> S,
             class Comp = ranges::less, class Proj = std::identity>
    requires std::sortable<I, Comp, Proj>
    constexpr I
        operator()(I first, S last, Comp comp = {}, Proj proj = {}) const
    {
        auto ret {ranges::next(first, last)};
        for (; first != last; --last)
            ranges::pop_heap(first, last, comp, proj);
        return ret;
    }

    template<ranges::random_access_range R, class Comp = ranges::less,
             class Proj = std::identity>
    requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
    constexpr ranges::borrowed_iterator_t<R>
        operator()(R&& r, Comp comp = {}, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), ranges::end(r), std::move(comp), std::move(proj));
    }
};

inline constexpr sort_heap_fn sort_heap {};

.SH Example


// Run this code

 #include <algorithm>
 #include <array>
 #include <iostream>

 void print(auto const& rem, auto const& v)
 {
     std::cout << rem;
     for (const auto i : v)
         std::cout << i << ' ';
     std::cout << '\\n';
 }

 int main()
 {
     std::array v {3, 1, 4, 1, 5, 9};
     print("original array:  ", v);

     std::ranges::make_heap(v);
     print("after make_heap: ", v);

     std::ranges::sort_heap(v);
     print("after sort_heap: ", v);
 }

.SH Output:

 original array:  3 1 4 1 5 9
 after make_heap: 9 5 4 1 1 3
 after sort_heap: 1 1 3 4 5 9

.SH See also

   ranges::is_heap       checks if the given range is a max heap
   (C++20)               (niebloid)
   ranges::is_heap_until finds the largest subrange that is a max heap
   (C++20)               (niebloid)
   ranges::make_heap     creates a max heap out of a range of elements
   (C++20)               (niebloid)
   ranges::pop_heap      removes the largest element from a max heap
   (C++20)               (niebloid)
   ranges::push_heap     adds an element to a max heap
   (C++20)               (niebloid)
                         turns a max heap into a range of elements sorted in ascending
   sort_heap             order
                         \fI(function template)\fP
